package 剑指专题.链表;


/*
 * Author：江松
 * Date：2023/3/26 11:19
 *
 1，哈希表，<序号，点>
 2，两次遍历
 3,快慢指针，严格O(n):fast领先k步，则fast为空时，slow就是倒数第k个
 */

public class Main6 {


    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode slow=pHead,fast=pHead;
        for(int i=0;i<k;++i){
            if(fast==null)return null;
            fast=fast.next;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }

    /*
    public ListNode FindKthToTail (ListNode pHead, int k) {
        int cnt=0;
        ListNode p=pHead;
        while(p!=null){
            p=p.next;
            cnt++;
        }
        if(k>cnt)return null;
        int i=cnt-k;
        p=pHead;
        while(i-->0){
            p=p.next;
        }
        return p;
    }
    */
}
